#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#define NOFOUND -1

int binary_search(int m[],int key,int n)
{
    int left,right,mid;
    left=0,right=n-1;
    while(left<=right)
    {
        mid=(left+right)/2;
        if(key==m[mid])  return mid;
        if(key<m[mid])  right=mid-1;
        else            left=mid+1;
    }
    return(NOFOUND);
}

int binary_search_recurrence(int m[],int key,int low,int high)
{
    int mid=(low+high)/2;
    if(low>high)        return NOFOUND;
    if(key==m[mid])     return mid;
    else if(key<m[mid])  return binary_search_recurrence(m,key,low,mid-1);
    else                 return binary_search_recurrence(m,key,mid+1,high);
}

int main()
{
    int n,x,len,out_recurrence,out_common;
    clock_t start, finish;
    double duration;
    printf("请输入查找模型数据大小：");
    scanf("%d",&n);
    printf("请输入查找模型数据样本：");
    int array[n];
    for(int i=0;i<n;i++)
    {
        scanf("%d",&array[i]);
    }
    printf("请输入需要查找的数据:");
    scanf("%d",&x);
    len=sizeof(array)/sizeof(array[0]);

    start=clock();
    out_common=binary_search(array,x,len);
    finish=clock();
    printf("找到数据,位置为%d\n",out_common);
    duration = (double)(finish - start) / CLOCKS_PER_SEC;    //CLOCKS_PER_SEC这个量与操作系统相关
    printf("常规二分查找耗时：%f\n",duration);

    start=clock();
    out_recurrence=binary_search_recurrence(array,x,0,len-1);
    finish=clock();
    printf("找到数据,位置为%d\n",out_recurrence);
    duration = (double)(finish - start) / CLOCKS_PER_SEC;
    printf("递归二分查找耗时：%f",duration);
}